Skip to main content

第65章 图论算法及综合应用

图论算法是处理复杂关系问题的核心工具，其中最小生成树（MST）和单源最短路是两类经典问题。最小生成树用于在连通图中寻找总权值最小的连通子图，单源最短路则用于计算从一个起点到其他所有顶点的最短路径。

65.1 最小生成树(Minimum Spanning Tree, MST)​

65.1.1 基本概念​

生成树定义：对于连通无向图，生成树是包含全部nn个顶点u、v恰好n−1n-1条边且无环的连通子图。 最小生成树定义：带权连通无向图中，所有生成树里边权总和最小的那一棵。 核心性质：

  1. 最小生成树不一定唯一，但总权值固定；
  2. 边数恒为n−1n-1，保证全图连通。

65.1.2 Kruskal算法​

算法原理：贪心策略，先把所有边按权升序排序，依次选边，使用并查集规避环，选满n−1n-1条边停止。 执行步骤：

  1. 全部边从小到大排序；
  2. 初始化并查集，每个顶点自成集合；
  3. 遍历每条边(u,v)(u,v)：若uu、vvuu、vv不在同一集合，加入生成树，合并集合；
  4. 累计选中边至n−1n-1条，结束。
#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>
using namespace std;

// 并查集结构
struct UnionFind{
    vector<int> parent;
    vector<int> rank;
    UnionFind(int n){
        parent.resize(n);
        rank.resize(n, 0);
        for(int i = 0; i < n; ++i){
            parent[i] = i;
        }
    }
    // 路径压缩查找根
    int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    // 按秩合并
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]){
            parent[x] = y;
        }else{
            parent[y] = x;
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
};

// Kruskal求最小生成树，返回总权值，不连通返回-1
int kruskal(int n, vector<tuple<int, int, int>>& edges) {
    sort(edges.begin(), edges.end(), [](const tuple<int,int,int>&a, const tuple<int,int,int>&b){
        return get<2>(a) < get<2>(b);
    });
    UnionFind uf(n);
    int totalWeight = 0;
    int edgeCount = 0;
    for(auto& e : edges){
        int u = get<0>(e);
        int v = get<1>(e);
        int w = get<2>(e);
        if(uf.find(u) != uf.find(v)){
            uf.unite(u, v);
            totalWeight += w;
            edgeCount++;
            if(edgeCount == n-1) break;
        }
    }
    return edgeCount == n-1 ? totalWeight : -1;
}

算法复杂度：O(elog⁡e)O(e \log e)，适合稀疏图。

65.1.3 Prim算法​

算法原理：从任意顶点开始维护生成树集合，每次选取连接树内外权值最小的边扩展。 执行步骤：

  1. 初始化lowCost数组，记录各点到当前树的最小边权；起点权值置0；
  2. 循环选出不在树中u、vlowCost最小的顶点加入树；
  3. 用该点更新所有邻点的lowCost；
  4. 全部顶点入树则结束。
#include <vector>
#include <climits>
using namespace std;

// 邻接矩阵版Prim，返回总权，不连通返回-1
int prim(int n, const vector<vector<int>>& graph){
    const int INF = INT_MAX;
    vector<int> lowCost(n, INF);
    vector<bool> inMST(n, false);
    lowCost[0] = 0;
    int totalWeight = 0;
    int count = 0;
    for(int i = 0; i < n; ++i){
        int u = -1;
        int minW = INF;
        // 找未入树最小权顶点
        for(int v = 0; v < n; ++v){
            if(!inMST[v] && lowCost[v] < minW){
                minW = lowCost;
                u = v;
            }
        }
        if(u == -1) return -1;
        inMST[u] = true;
        totalWeight += minW;
        count++;
        // 更新邻接点代价
        for(int v = 0; v < n; ++v){
            if(!inMST[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]){
                lowCost[v] = graph[u][v];
            }
        }
    }
    return count == n ? totalWeight : -1;
}

复杂度：邻接矩阵O(n2)O(n^2)，适合稠密图。

65.1.4 Kruskal与Prim对比​

算法核心思路稀疏图复杂度稠密图复杂度适用场景
Kruskal排序选边，并用并查集避环O(elog⁡e)O(e\log e)O(elog⁡e)O(e\log e)边少的稀疏图
Prim逐步扩展生成树O(elog⁡n)O(e\log n)O(n2)O(n^2)顶点少稠密图

65.2 单源最短路(Single-Source Shortest Paths)​

65.2.1 基础定义​

单源最短路：给定起点ss，求ss到其余所有顶点的最短路径总权。 负权边：边权小于0；负权环：环总权为负，存在则无最短路径。

65.2.2 Dijkstra算法​

适用：无负权图，贪心策略，优先队列优化。

#include <vector>
#include <queue>
#include <climits>
using namespace std;

vector<int> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int s){
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        auto cur = pq.top();
        pq.pop();
        int u = cur.second;
        if(visited[u]) continue;
        visited[u] = true;
        for(auto& edge : adj[u]){
            int v = edge.first;
            int w = edge.second;
            if(dist[u] != INF && dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

复杂度：O((n+e)log⁡n)O((n+e)\log n)，不能处理负权。

65.2.3 Floyd算法​

动态规划，求任意两点间最短路，允许负权（无负环）。

#include <vector>
#include <iostream>
#include <climits>
using namespace std;
const int INF = INT_MAX / 2;

void floyd(int n, vector<vector<int>>& dist) {
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                if(dist[i][k] + dist[k][j] < dist[i][j]){
                    dist[i][j] = dist[i][k] + dist[k];
                }
            }
        }
    }
}

复杂度O(n3)O(n^3)，顶点数量少时使用。

65.2.4 Bellman-Ford算法​

支持负权，可检测负权环，对全部边循环松弛n−1n-1次。

#include <vector>
#include <tuple>
#include <climits>
using namespace std;

pair<vector<int>, bool> bellmanFord(int n, const vector<tuple<int,int,int>>& edges, int s){
    const int INF = INT_MAX;
    vector<int> dist(n, INF);
    dist[s] = 0;
    bool hasNegativeCycle = false;
    // n-1轮松弛
    for(int i = 0; i < n-1; ++i){
        bool update = false;
        for(auto& e : edges){
            int u = get<0>(e);
            int v = get<1>(e);
            int w = get<2>(e);
            if(dist[u] != INF && dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                update = true;
            }
        }
        if(!update) break;
    }
    // 检测负环
    for(auto& e : edges){
        int u = get<0>(e);
        int v = get<1>(e);
        int w = get<2>(e);
        if(dist[u] != INF && dist[v] > dist[u] + w){
            hasNegativeCycle = true;
            break;
        }
    }
    return {dist, hasNegativeCycle};
}

复杂度O(n×e)O(n \times e)，效率偏低，适合小规模带负权图。

65.3 算法对比总结​

  1. MST：稀疏用Kruskal，稠密用Prim；
  2. 单源最短路无负权选Dijkstra；
  3. 全点最短路u、v允许负权无环选Floyd；
  4. 需要判断负环使用Bellman-Ford。